public class KnapsackTest
{
    public static void main(String [] args)
    {
        int w[]={2,2,6,5,4};
        int v[]={6,3,5,4,6};
        int W0=10;
        Knapsack ks=new Knapsack(w, v, W0);
        ks.solve();

    }
}
class Knapsack
{
    int w[];//重量
    int v[];//价值
    int V[][];//V[i][j]表示物品0,1,...i放入限重j的背包所能获取的最大价值
    int c[];//c[i]=0表示选择物品i,c[i]=0表示不选物品i
    int W;//限重

    public Knapsack(int w0[],int v0[],int W0)
    {
        w=w0;
        v=v0;
        W=W0;
    }
    private void MaximizeValue()
    {
        V=new int[w.length][W+1];
        for(int j=0;j<=W;j++)
        {
            if(j>=w[0])
            {
                V[0][j]=v[0];
            }
            else
            {
                V[0][j]=0;
            }
        }
        for(int i=0;i<w.length;i++)
        {
            V[i][0]=0;
        }
        for(int i=1;i<w.length;i++)
        {
            for(int j=1;j<=W;j++)
            {
                if(j>=w[i]&&((V[i-1][j-w[i]]+v[i])>V[i-1][j]))
                {
                    V[i][j]=V[i-1][j-w[i]]+v[i];
                }
                else
                {
                    V[i][j]=V[i-1][j];
                }
            }
        }
    }
    private void Choose(int i,int j)
    {
        
        if(i==0)
        {
            if(j>=w[0])
                c[0]=1;
            else
                c[0]=0;
            return ;
        }
        if(V[i][j]!=V[i-1][j])
        {
            c[i]=1;
            Choose(i-1,j-w[i]);
        }
        else
        {
            c[i]=0;
            Choose(i-1,j);
        }
    }
    public void solve()
    {
        MaximizeValue();
        // for(int i=0;i<w.length;i++)
        // {
        //     for(int j=0;j<=W;j++)
        //     {
        //         System.out.printf("%d ",V[i][j]);
        //     }
        //     System.out.printf("\n");
        // }
        System.out.printf("最大价值:%d\n",V[w.length-1][W]);
        c=new int[w.length];
        Choose(w.length-1,W);
        System.out.printf("选择的物品:");
        for(int i=0;i<w.length;i++)
        {
            if(c[i]==1)
            {
                System.out.printf("%d ",i+1);
            }
        }
        System.out.println();
    }

}